"""
素数伴侣_牛客题霸_牛客网
https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e


>>> [I][O]
4
2 5 6 13
---
2

22
20923 22855 2817 1447 29277 19736 20227 22422 24712 27054 27050 18272 5477 27174 13880 15730 7982 11464 27483 19563 5998 16163
---
8

2
3 6
---
0
"""


def handle(n: int, ar: list):
    def is_prime(n: int):
        if n <= 3:
            return n > 1
        if n & 1 == 0:
            return False

        for i in range(3, int(n**0.5) + 1, 2):
            if n % i == 0:
                return False
        return True

    def cp_them(e_i: int, odds_used: list):
        """
        匈牙利算法: 先到先得 能让就让
        """
        for o_i in range(len(odds)):
            # odds_used[]: prevent recursion from going too deep
            if odds_used[o_i] == -1 and is_prime(eves[e_i] + odds[o_i]):
                odds_used[o_i] = 1  # 当前元素已匹配

                if odds_cp_even[o_i] == -1 or cp_them(odds_cp_even[o_i], odds_used):
                    odds_cp_even[o_i] = e_i
                    return True
        return False

    odds = []
    eves = []

    for i in ar:
        if i & 1 == 1:
            odds.append(i)
        else:
            eves.append(i)

    odds_cp_even = [-1] * len(odds)
    cnt = 0

    for i in range(len(eves)):
        if cp_them(i, [-1] * len(odds)):
            cnt += 1

    return cnt


def handle_my(n: int, ar: list) -> int:
    def is_prime(n: int) -> bool:
        if n <= 1:
            return False
        if n <= 3:
            return True
        if n % 2 == 0 or n % 3 == 0:
            return False
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
        return True

    odd_list = [i for i in ar if i & 1]  # 奇数
    even_list = [i for i in ar if not (i & 1)]  # 偶数

    even_used = [-1] * len(even_list)

    def find_even_match(i: int, eut: list):
        for j in range(len(even_list)):
            if eut[j] == -1 and is_prime(odd_list[i] + even_list[j]):
                eut[j] = 1

                # 如果当前偶数没有匹配，或者匹配的奇数可以找到新的偶数匹配
                if even_used[j] == -1 or find_even_match(even_used[j], eut):
                    even_used[j] = i
                    return True
        return False

    cnt = 0
    for i in range(len(odd_list)):
        if find_even_match(i, [-1] * len(even_list)):
            cnt += 1
    return cnt


def main():
    n = input()
    ar = list(map(int, input().split()))

    res = handle_my(n, ar)

    print(res)


if __name__ == "__main__":
    main()
